package leetcode_700;

/**
 *@author 周杨
 *StrangePrinter_664 奇怪的打印机只能打印重复字符 但是打印的时候可以从任意起点和任意结束点打印 可以覆盖原有
 *describe:用动态规划 AC 10%
 *2018年9月28日 下午1:38:27
 */
public class StrangePrinter_664 {
	public int strangePrinter(String s) {
        int size = s.length();
        int[][] dp = new int[size + 1][size + 1];
        for (int x = 1; x <= size; x++) {
            for (int y = 1; y <= x; y++) {
                dp[y][x] = x - y + 1;
                for (int z = y; z < x; z++) {//判断这里覆盖需要的次数
                    dp[y][x] = Math.min(dp[y][x], dp[y][z - 1] + dp[z][x - 1] + 
                            (s.charAt(x - 1) != s.charAt(z - 1) ? 1 : 0));
                }
            }
        }
        return size > 0 ? dp[1][size] : 0;
    }
}
